package cn.suchan.jianzhi.sort;

/**
 * 堆排序
 * （没心情看，不理解，这样写是有问题的）
 *
 * @author suchan
 * @date 2019/06/18
 */
public class HeapSort {
    private int len = 0;

    public void sort(int[] array) {
        len = array.length;
        if (len <= 1) {
            return;
        }
        // 构建一个大顶堆
        buildMaxHeap(array);
        // 循环将堆首位（最大值），与末位交换，然后再重新调整最大堆
        while (len > 0) {
            swap(array, 0, len - 1);
            len--;
            adjustHeap(array, 0);
        }
    }

    /**
     * 构建大顶堆
     *
     * @param array
     */
    public void buildMaxHeap(int[] array) {
        // 从最后一个非叶子节点开始向上构造最大堆
        for (int i = (array.length - 1) / 2; i >= 0; i--) {
            adjustHeap(array, i);
        }
    }

    /**
     * 调整使之成为最大堆
     *
     * @param array
     * @param i
     */
    public void adjustHeap(int[] array, int i) {
        //int len = array.length;
        int maxIndex = i;

        //如果有左子树，且左子树大于父节点，则将最大指针指向左子树
        if (i * 2 < len && array[i * 2] > array[maxIndex]) {
            maxIndex = i * 2;
        }

        //如果有右子树，且右子树大于父节点，则将最大指针指向右子树
        if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex]) {
            maxIndex = i * 2 + 1;
        }

        //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
        if (maxIndex != i) {
            swap(array, maxIndex, i);
            adjustHeap(array, maxIndex);
        }
    }

    public void swap(int[] array, int i, int j) {
        int temp = array[0];
        array[0] = array[array.length - 1];
        array[array.length - 1] = temp;
    }

    public static void main(String[] args) {
        int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        HeapSort sort = new HeapSort();
        sort.sort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.printf(array[i] + " ");
        }
    }
}
